#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>

//开辟空的链表
//头节点：数据段为空，地址段为NULL用于做循环结束的条件
linknode_t *linklist_create()
{
    linknode_t *head = (linknode_t *)malloc(sizeof(linknode_t)); //开辟头节点的空间
    head->next = NULL;

    return head;
}

//头插入
int linklist_insert_head(linknode_t *head, data_t value)
{
    if (head == NULL)
        return -1;
    linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t)); //开辟新节点的空间
    node->data = value;                                          //数据段存储数据

    node->next = head->next; //新节点与第一个节点相连
    head->next = node;       //头节点与新节点相连

    return 0;
}

//尾插入
int linklist_insert_tail(linknode_t *head, data_t value)
{
    if (head == NULL)
        return -1;
    linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t)); //开辟新节点的空间
    node->data = value;
    node->next = NULL;
    linknode_t *current = head;
    while (current->next != NULL)
    {
        current = current->next; //循环让指针向后移动
    }                            //结束循环时head指向最后一个节点

    current->next = node; //最后一个节点与新节点相连

    return 0;
}
//按位置插入
int linklist_insert_pos(linknode_t *head, int pos, data_t value)
{
    if (head == NULL || pos < 1)
    {
        puts("pos error");
        return -1;
    }

    linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t)); //开辟新节点的空间
    node->data = value;
    linknode_t *current = head;
    int i;
    for (i = 1; i < pos && current->next != NULL; i++) //如果pos过大直接插入到最后一个位置
    {
        current = current->next; //循环让指针向后移动
    }                            //循环结束时，head指向前一个节点

    node->next = current->next; //新节点与后一个节点相连
    current->next = node;       //前一个节点与新节点相连

    return 0;
}

//按顺序插入(递增)
int linklist_insert_sort(linknode_t *head, data_t value)
{
    if (head == NULL)
        return -1;
    linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t));
    node->data = value;
    linknode_t *current = head;
    //	while(current->next->data < value && current->next != NULL) 		//错误
    while (current->next != NULL && current->next->data < value) //正确，短路原则
    {
        current = current->next;
    }

    node->next = current->next; //新节点与后一个节点相连
    current->next = node;       //前一个节点与新节点相连

    return 0;
}

//头删除
int linklist_delete_head(linknode_t *head)
{
    if (head == NULL)
        return -1;
    if (linklist_is_empty(head))
    {
        puts("empty");
        return -1;
    }

    linknode_t *temp = head->next; //临记录要删除的节点(第一个节点)
    head->next = temp->next;       //head->next = head->next->next;
                                   //头节点与第二个节点相连
    free(temp);                    //释放temp所代表的第一个节点空间
    temp = NULL;                   //防止野指针

    return 0;
}

//尾巴删除
int linklist_delete_tail(linknode_t *head)
{
    if (head == NULL)
        return -1;
    if (linklist_is_empty(head))
    {
        puts("empty");
        return -1;
    }
    linknode_t *current = head;
    while (current->next->next != NULL)
    {
        current = current->next; //循环让指针向后移动
    }                            //结束循环时head指向最后一个节点

    linknode_t *temp = current->next; //临记录要删除的节点(最后一个节点)
    current->next = temp->next;       //head->next = head->next->next;

    free(temp);  //释放temp所代表的最后一个节点空间
    temp = NULL; //防止野指针
    return 0;
}

//通用删除
int linklist_delete_pos(linknode_t *head, int pos)
{
    int i = 1;
    if (head == NULL)
        return -1;
    if (linklist_is_empty(head))
    {
        puts("empty");
        return -1;
    }
    linknode_t *current = head;
    while (i < pos && current->next != NULL) // i < pos && head->next != NULL
    {
        current = current->next; //循环让指针向后移动
        i++;
    }                                 //结束循环时head指向最后一个节点
    linknode_t *temp = current->next; //临记录要删除的节点(最后一个节点)
    current->next = temp->next;       //head->next = head->next->next;

    free(temp);  //释放temp所代表的最后一个节点空间
    temp = NULL; //防止野指针

    return 0;
}

//判断为空返回1  非空返回0
int linklist_is_empty(linknode_t *head)
{
    if (head == NULL)
        return -1;
    return head->next == NULL ? 1 : 0;
}
//修改
int linklist_change(linknode_t *head, data_t old, data_t new)
{
    if (head == NULL)
        return -1;
    while (head->next != NULL)
    {
        head = head->next;     //指针向后移动一个节点
        if (head->data == old) //判断是否是要修改的数据
        {
            head->data = new; //修改数据
        }
    }

    return 0;
}
data_t linklist_get(linknode_t *head, int pos)
{
    int i = 0;
    if (head == NULL || pos < 0)
        return -1;
    linknode_t *current = head;
    while (current->next != NULL && i < pos)
    {
        current = current->next;
        i++;
    }

    return current->data;
}
//数据翻转
int linklist_revers(linknode_t *head)
{
    if (head == NULL)
        return -1;
    linknode_t *temp = NULL;
    linknode_t *old = head->next; //old：无头的旧链表
    head->next = NULL;            //head：新链表

    while (old != NULL) //有头和无头判断的条件不一样
    {
        temp = old;      //临时记录要删除的节点
        old = old->next; //头删除法

        temp->next = head->next; //头插入法
        head->next = temp;
    }

    return 0;
}

//遍历
int linklist_show(linknode_t *head)
{
    if (head == NULL)
        return -1;
    while (head->next != NULL)
    {
        head = head->next;          //指针向后移动一个节点
        printf("%d  ", head->data); //打印节点里的数据
    }
    putchar(10);

    return 0;
}
